/**
 * BigestSubBST.java created by zhangzhidong 
 * at 下午12:09:04 2016年4月23日
 */
package algorithm.CIG.binarytree;

import java.util.HashMap;

import algorithm.CIG.base.TreeNode;

/**
 * @author zhangzhidong
 *
 */
public class MaxLengthPath extends VisualTree{
	public static int getBiggestLength(TreeNode tn,int sum){
		HashMap<Integer,Integer> map = new HashMap<>();
		map.put(0, 0);
		return preOrder(tn, sum,0,1,0,map);
	}
	private static int preOrder(TreeNode head,int sum,int preSum,int level,int maxLen,HashMap<Integer, Integer>map){
		if(head==null)
			return maxLen;
		int val = head.val;
		 int curSum =  preSum + val;
		 if(!map.containsKey(curSum)){
			 map.put(curSum, level);
		 }
		 if(map.containsKey(curSum-sum)){
			 maxLen = Math.max(maxLen, level-map.get(curSum-sum));
		 }
		 maxLen  = preOrder(head.left, sum, curSum, level+1, maxLen, map);
		 maxLen  = preOrder(head.right, sum, curSum, level+1, maxLen, map);
		if(level==map.get(curSum)){
			map.remove(curSum);
		}
		return maxLen;
	}
	public static void main(String args[]){	
		TreeNode head = generateTree();
		printTree(head);
		System.out.println("================================");
		System.out.println(getBiggestLength(head, 34));
	}
	public static TreeNode generateTree(){
		TreeNode head = new TreeNode(6);
		head.left = new TreeNode(1);
		head.left.left = new TreeNode(0);
		head.left.right = new TreeNode(3);
		head.right = new TreeNode(12);
		head.right.left = new TreeNode(10);
		head.right.left.left = new TreeNode(4);
		head.right.left.left.left = new TreeNode(2);
		head.right.left.left.right = new TreeNode(5);
		head.right.left.right = new TreeNode(14);
		head.right.left.right.left = new TreeNode(11);
		head.right.left.right.right = new TreeNode(15);
		head.right.right = new TreeNode(13);
		head.right.right.left = new TreeNode(20);
		head.right.right.right = new TreeNode(16);
		return head;
	}
}
